"""
双向链表相对于单向链表，无非在链表节点上增加：
链表节点：组成链表中的各个节点，分成两部分：1）自身数据；2）下一个数据；3）上一个数据。
链表指针：链表头和链表尾。1）链表头指向了最开始的那个节点；2）链表尾指向了最后结束的那个节点。这个不变

列表指针的规律为：
self.head=none
self.tail=none

插入一个5 [5]
self.head=5
self.tail=5

插入一个7 [5,7]
self.head=5
self.tail=7

插入一个9 [5,7,9]
self.head=5
self.tail=9
所以这里，链表头没有变化，链表尾一直在变化。和单向链表没有区别
"""


class SingleNode:
    '''
    链表中的一个节点，包含自身数据和下一个数据
    '''

    def __init__(self, val, next=None, prev=None):
        self.val = val  # 当前节点的值
        self.next = next  # 当前节点后面节点的值
        self.prev = prev  # 当前节点前面节点的值

    def __repr__(self):
        return str(self.val)


class LinkedList:
    '''
    链表容器，来存放每一个节点，包含链表节点，容器头和容器尾
    容器头指向容器中第一个节点，容器尾指向容器中最后一个节点
    '''

    def __init__(self):
        self.head = None  # 准备这个保存的是SingleNode实例
        self.tail = None  # 准备这个保存的是SingleNode实例

    def append(self, val):
        node = SingleNode(val)  # 将类SingleNode实例化，当前实例为node

        if self.tail is None:  # 如果tail是none则表示该节点是容器中第一个节点
            self.head = node  # 容器头为容器中第一个节点
        else:  # 该节点是容器中非第一个节点
            self.tail.next = node  # 将上一个节点的next设置为自己
            node.prev = self.tail  # 将自己的prev设置为上一个节点

        self.tail = node  # 重写tail为自己，为下一次append做准备。

    def iternodes(self, reverse=False):  # 遍历容器，增加倒叙功能
        current = self.tail if reverse else self.head
        while current:
            yield current
            current = current.prev if reverse else current.next

    # 增加一个pop功能
    def pop(self):
        if self.tail is None:
            raise Exception('Empty')

        popnode = self.tail  # 最后一个节点
        popnode_prev = popnode.prev  # 最后一个节点的前一个值

        if popnode_prev is None:  # 表明链表中就一个节点
            self.tail = None
            self.head = None
        else:  # 表明链表中非一个节点
            self.tail = popnode_prev  # 容器尾指向最后一个节点的前一个值
            popnode_prev.next = None  # 最后一个节点的前一个值的next设置为None

        return popnode.val  # 返回最后一个节点的值

    # 增加一个get功能
    def getitem(self, index):  # 查询功能，等价"def __getitem__(self, item):"
        if index < 0:  # 不支持负索引功能
            return None

        current = None  # 定义查询变量并初始化
        for i, node in enumerate(self.iternodes()):  # 遍历链表，如果能找到，就给查询遍历赋值
            if i == index:
                current = node
                break

        if current is None:  # 说明没找到
            return None
        else:  # 说明找到了
            return current

    # 增加一个insert功能
    def insert(self, index, val):  # index用来定义参考节点，val用来定义插入节点，val会插入到index前面
        if index < 0:  # 说明不支持负索引
            raise ValueError('Wrong index {}'.format(index))

        current = None  # current变量用来装被索引查询到的参考节点
        for i, node in enumerate(self.iternodes()):  # 遍历链表
            if i == index:
                current = node
                break

        if current is None:  # 说明链表中没找到，在尾部追加
            self.append(val)  # 这里调用了自定义的append方法

        # 说明链表中找到了
        node_val = SingleNode(val)  # 初始化插入节点

        # 针对参考节点，进行判断
        if current.prev is None:  # 参考节点前面没有节点
            self.head = node_val  # 链表头指向插入节点
            node_val.next = current  # 插入节点的下一个值为参考节点
            current.prev = node_val  # 参考节点的前一个值为插入节点
        else:  # 参考节点在中间或者结尾
            node_val.prev = current.prev  # 插入节点的前一个值为参考节点的前一个值
            node_val.next = current  # 插入节点的下一个值为参考节点
            current.prev = node_val  # 参考节点的前一个值为插入节点
            current.prev.next = node_val  # 参考节点的前一个值的下一个值为插入节点

    # 增加一个remove功能
    def remove(self, index):
        if index < 0:
            raise ValueError('Wrong index {}'.format(index))
        if self.tail is None:
            raise Exception('empty')

        current = None  # 定义查询变量并初始化
        for i, node in enumerate(self.iternodes()):  # 遍历链表，如果能找到，就给查询遍历赋值
            if i == index:
                current = node
                break

        if current is None:  # 被删除的节点在链表中没有找到
            raise ValueError('Wrong index {}, out of boundary'.format(index))

        # 被删除的节点在链表中找到了
        # 针对被删除的节点，进行判断
        if current.prev is None and current.next is None:  # 链表中只有一个
            self.head = None
            self.tail = None
        elif current.prev is None:  # 被删除的节点在开头
            self.head = current.next
            current.next.prev = None
        elif current.next is None:  # 被删除的节点在结尾
            self.tail = current.prev
            current.prev.next = None
        else:  # 被删除的节点在中间
            current.prev.next = current.next
            current.next.prev = current.prev

        del current


# 初始化
a = LinkedList()

# 测试
a.append(12)
a.append(13)
a.append(14)
a.append(15)
a.append(16)

for x in a.iternodes(reverse=True):
    print(x)

a.pop()
a.pop()

for x in a.iternodes(reverse=True):
    print(x)

print('No.{} is {}'.format(4, a.getitem(4)))

a.insert(3, 1000)
for x in a.iternodes(reverse=True):
    print(x)

a.remove(3)
for x in a.iternodes(reverse=True):
    print(x)
